package first.niuke.simple;

/**
 * @ClassName NC7
 * @description:
 * @author: 荣燊
 * @create: 2021-06-02 10:01
 **/
public class NC7 {
    // 使用动态规划的，最好找到转移方程
    // 假设第i天持有股票的收益是 f(i,1), 未持有股票是f(i,0)
    // f(i,0) = max(f(i-1, 0), f(i-1, 1)+prices[i])
    // f(i,1) = max(f(i-1, 1), f(i-1, 0)-prices[i])
    // 对于f(i,1)因为只能买一次所以f(i-1,0)=0
    // f(i,1) = max(f(i-1, 1), 0-prices[i])
    public static int maxProfit (int[] prices) {
        // write code here
        if (prices.length < 2) {
            return 0;
        }
        int i0 = 0, i1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            // 未持有的收益，持有的最大价格与当前价格比较
            i0 = Math.max(i0, i1 + prices[i]);
            // 价格的最小值
            i1 = Math.max(i1, -prices[i]);
        }
        return i0;
    }

    public static void main(String[] args) {
        int[] a = {1, 4, 2};
        System.out.println(maxProfit(a));
    }
}
